Arithmetic progressions in subsetsums of sparse random sets of integers

Abstract: Given a set $S\subset\mathbb{N}$, its sumset $S+S$ is the set of all sums $s+s'$ with both $s$ and $s'$ elements of $S$. Given $p \colon \mathbb{N}\to [0,1]$, let $A_n=[n]_p$ be the $p$-random subset of $[n]=\{1,\dots,n\}$: the random set obtained by including each element of $[n]$ in $A_n$ independently with probability $p(n)$. Let $\varepsilon>0$ be fixed, and suppose $p(n)\geq n^{-1/2+\varepsilon}$ for all large enough $n$. We prove that, then, with high probability, long arithmetic progressions exist in the sumset of any positive density subset of $A_n$, that is, with probability approaching $1$ as $n\to\infty$, for any subset $S$ of $A_n$ with a fixed proportion of the elements of $A_n$, the sumset $S+S$ contains arithmetic progressions with $2^{\Omega(\sqrt{\log n})}$ elements. Joint work with Marcelo Campos and Gabriel Dahia.

Mathematics

Audience: researchers in the topic

Combinatorial and additive number theory (CANT 2025)